package com.leetcode.LC_MED;

public class LC91 {
    public int numDecodings(String s) {
        //从后往前，识别最后两个字符
        char[] chars = s.toCharArray();
        int[] dp = new int[s.length() + 1];
        dp[0] = 1;
        for (int i = 1; i <= s.length(); i++) {
            if (chars[i - 1] != '0') {
                dp[i] += dp[i - 1];
            }
            if (i >= 2) {
                int t = (chars[i - 2] - '0') * 10 + chars[i - 1] - '0';
                if (t >= 10 && t <= 26) {
                    dp[i] += dp[i - 2];
                }
            }
        }
        return dp[dp.length - 1];
    }

    public static void main(String[] args) {
        System.out.println(new LC91().numDecodings("12"));
    }
}
